#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:

    int citys(vector<vector<int> >& m) {
        int n = 1;
        vector<set<int>> citytrees(1);
        for (int i = 0; i < m[0].size(); i++) if (m[0][i]) citytrees[0].insert(i);
        for (int i = 1; i < m.size(); i++)
        {
            int j;
            for (j = 0; j < i; j++) if (m[i][j]) break;
            cout << i << "->" << j << endl;
            if (j < i)
            {
                vector<int> treenum;
                for (int x = 0; x < citytrees.size(); x++)
                    if (citytrees[x].find(i) != citytrees[x].end()) treenum.push_back(x);

                for (int y = 1; y < treenum.size(); y++)
                {
                    for (auto z : citytrees[treenum[y]]) citytrees[treenum[0]].insert(z);
                    citytrees[treenum[y]].erase(citytrees[treenum[y]].begin(), citytrees[treenum[y]].end());
                }
                cout << treenum.size() << ' ';
                n -= treenum.size() - 1;
                for (int k = i; k < m[i].size(); k++) if (m[i][k]) citytrees[treenum[0]].insert(k);
            }
            else
            {
                n++;
                set<int> tmp;
                for (int k = j; k < m[i].size(); k++) if (m[i][k]) tmp.insert(k);
                citytrees.push_back(tmp);
            }
        }
        return n;
    }
};